{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# _Scalar Chains_\n",
    "\n",
    "<img src=\"images/line_circs_site_psi.png\" alt=\"Scalar Chain\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Contributor\n",
    "Alexander Yu. Vlasov\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The notebook describes some applications of scalar chain. The examples with _discrete quantum walk_ on a scalar chain are discussed further:\n",
    "- [Coined quantum walk](#coined_walk) – discrete quantum walk with coin\n",
    "- [Staggered quantum walk](#staggered_walk) – and equivalent model with alternating steps\n",
    "- [Modeling of quantum walk on scalar chain](#modeling) – Python modeling\n",
    "\n",
    "Scalar chain with $N$ nodes is a quantum system with basic states $|k\\rangle$, $k=1,\\dots,N$. \n",
    "Let us denote $R$ and $L$ operators of right and left shift respectively. For an infinite chain without boundary:\n",
    "\n",
    "$$R : |k\\rangle \\to |k+1\\rangle,\\qquad L : |k\\rangle \\to |k-1\\rangle.$$\n",
    "\n",
    "For a cyclic boundary condition (motion on a ring) arithmetic modulo $N$ should be used instead and an alternative model with possibility of reflections is considered further.\n",
    "\n",
    "The model of scalar chain is convenient for description of _quantum walk_. There are two broad classes of quantum walks: discrete and continuous (_aka_ state transport). The examples below use discrete time models and  _'quantum bots'_ together with _coined_ and _staggered_ discrete quantum walk – are simple illustrations of such approach.\n",
    "\n",
    "### _Coined quantum walk_<a id='coined_walk'></a>\n",
    "\n",
    "Let us consider so-called _coined quantum walk_. The model uses (together with a chain $|k\\rangle$, $k=1,\\dots,N$) the special _coin_ $|c\\rangle$ with two states $|0\\rangle$ and $|1\\rangle$ to control direction of walk. So, basic states of the model are defined as $|c\\rangle|k\\rangle$.\n",
    "\n",
    "The coin defines direction of motion using _controlled shift_ operator:\n",
    "\n",
    "$$S = |0\\rangle\\langle 0| \\otimes R + |1\\rangle\\langle 1| \\otimes L$$\n",
    "\n",
    "Such a model (_aka quantum bot_) is an example of _conditional quantum dynamics_. The operator $S$ for basic states of coins $|0\\rangle$ and $|1\\rangle$ produces right and left shifts respectively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/lines_quantum_bot.png\" alt=\"Quantum Bot\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The coined quantum walk suggests modification of coin after each step $S$ using some operator $C$ on a two-dimensional \"coin space\"\n",
    "\n",
    "$$W = S \\cdot (C \\otimes {\\bf 1})$$\n",
    "\n",
    "to look for some analogue of classical random walk.\n",
    "Simplest choise is Hadamard matrix:\n",
    "\n",
    "$$C_H = H = \\frac{\\sqrt 2}{2}\\begin{pmatrix}1&1\\\\1&-1\\end{pmatrix}.$$\n",
    "\n",
    "A _balanced coin_ also may be used\n",
    "\n",
    "$$C_b = \\frac{\\sqrt 2}{2}\\begin{pmatrix}1&i\\\\i&1\\end{pmatrix}.$$\n",
    "\n",
    "The model also permits to define reflection on boundaries. In such a case operator $S$ should \"loop\" both chains with opposite directions of motion:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/loop_quantum_bot.png\" alt=\"Walk with Reflections\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### _Staggered quantum walk_<a id='staggered_walk'></a>\n",
    "\n",
    "The composite quantum system with coin and chain has $2\\times N = 2N$ basic states $|c,k\\rangle$. An equivalent model of _staggered quantum walk_ is defined on a chain with $2N$ nodes and special partitions. Let us consider for $k =1,2,\\ldots$ first partition with pairs of states $(2k-1,2k)$ and the second one with $(2k,2k+1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/line_circs_part.png\" alt=\"Staggered Walk\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us denote $S_1$ and $S_2$ swaps in all pairs for first and second partition, respectively. Without taking into account boundary, the composition of alternating swaps \n",
    "$S = S_1 S_2$ would produce double-step shifts of elements with even and odd indexes in opposite directions $2k \\to 2k+2$ and $2k+1 \\to 2k-1$. \n",
    "\n",
    "See <a href=\"https://qubeat.github.io/staggered-walk/\">animated staggered classical walk in 3D</a> for illustration of such a motion with boundary effects. \n",
    "\n",
    "For a quantum model states $|c,k\\rangle$ are mapped into $|2k+1\\rangle$. The trivial motion of basic states would be represented as $S = S_1 S_2$, where $S_1 = s(1,2)\\,s(3,4)\\dots$ and $S_2 = s(2,3)\\,s(4,5)\\dots$ are two alternating\n",
    "sequences of swaps defined for given link simply as\n",
    "\n",
    "$$s = \\begin{pmatrix}0&1\\\\1&0\\end{pmatrix}.$$ \n",
    "\n",
    "Coin operator $C$ acts on pairs in first partition $C = c(1,2)\\,c(3,4)\\dots$ and an operator\n",
    "$S^\\prime_1 = C S_1$ is used in quantum staggered walk\n",
    "\n",
    "$$W_S = S^\\prime_1\\,S_2 = (C S_1) S_2.$$\n",
    "\n",
    "So, for single link a swap operator multiplied on Hadamard coin is\n",
    "\n",
    "$$s_c = c \\, s = \\frac{\\sqrt 2}{2}\\begin{pmatrix}1&-1\\\\1&1\\end{pmatrix}.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### _Modeling of a quantum walk on scalar chain_<a id='modeling'></a>\n",
    "\n",
    "Models discussed further use one-to-one correspondence $n = N$ between qubits and nodes of chain \n",
    "(or $n = 2N$ for staggered walk).\n",
    "More difficult method could \"expand\" $n$ qubits into a scalar chain with $N = 2^n$ states, \n",
    "but it should be discussed elsewhere.\n",
    "Thus, the scalar quantum chain model may use standard packages such as NumPy to \n",
    "compare with Qiskit application for [qubit chain](qubit_chain.ipynb).\n",
    "\n",
    "See more in [notebook for scalar chain modeling](scalar_chain_mod.ipynb)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
